/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/add-binary
@Language: C++
@Datetime: 16-02-09 04:40
*/

class Solution {
public:
    /**
     * @param a a number
     * @param b a number
     * @return the result
     */
    void reverse(string &s){
        int i=s.length(),len=0;
        char str[1000];
        while(i--){
            str[len++]=s[i];
        }
        str[len++]='\0';
        s = str;
    }
    void reverse(char *s){
        int i=0,j=strlen(s)-1,t;
        while(i<j){
            t = s[i];
            s[i] = s[j];
            s[j]=t;
            i++,j--;
        }
    }
    string addBinary(string& a, string& b) {
        // Write your code here
        int dec=2,carry=0,len=0,i;
        char r[1000]={0};
        reverse(a);
        reverse(b);
        for(i=0;i<a.length() && i<b.length();++i,++len){
            r[len] = a[i]-'0'+b[i]+carry;
            carry = (r[len]-'0')/dec;
            r[len] = (r[len]-'0')%dec+'0';
        }
        for(;i<a.length();++i,++len){
            r[len] = a[i]+carry;
            carry = (r[len]-'0')/dec;
            r[len]=(r[len]-'0')%dec+'0';
        }
        for(;i<b.length();++i,++len){
            r[len] = b[i]+carry;
            carry = (r[len]-'0')/dec;
            r[len]=(r[len]-'0')%dec+'0';
        }
        if (carry)
            r[len++] = carry+'0';
        r[len]='\0';
        reverse(r);
        return r;
    }
};